{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Submatrices That Sum to Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSubmatrixSumTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #元素和为目标值的子矩阵数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出矩阵 <code>matrix</code> 和目标值 <code>target</code>，返回元素总和等于目标值的非空子矩阵的数量。</p>\n",
    "\n",
    "<p>子矩阵 <code>x1, y1, x2, y2</code> 是满足 <code>x1 <= x <= x2</code> 且 <code>y1 <= y <= y2</code> 的所有单元 <code>matrix[x][y]</code> 的集合。</p>\n",
    "\n",
    "<p>如果 <code>(x1, y1, x2, y2)</code> 和 <code>(x1', y1', x2', y2')</code> 两个子矩阵中部分坐标不同（如：<code>x1 != x1'</code>），那么这两个子矩阵也不同。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/02/mate1.jpg\" style=\"width: 242px; height: 242px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>四个只含 0 的 1x1 子矩阵。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[1,-1],[-1,1]], target = 0\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[904]], target = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong><strong>提示：</strong></strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= matrix.length <= 100</code></li>\n",
    "\t<li><code>1 <= matrix[0].length <= 100</code></li>\n",
    "\t<li><code>-1000 <= matrix[i] <= 1000</code></li>\n",
    "\t<li><code>-10^8 <= target <= 10^8</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-submatrices-that-sum-to-target](https://leetcode.cn/problems/number-of-submatrices-that-sum-to-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-submatrices-that-sum-to-target](https://leetcode.cn/problems/number-of-submatrices-that-sum-to-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,0],[1,1,1],[0,1,0]]\\n0', '[[1,-1],[-1,1]]\\n0', '[[904]]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            tot = [0] * (m+1)\n",
    "            for k in range(i, n):\n",
    "                cnt = Counter([0])\n",
    "                prv = 0\n",
    "                for j in range(m):\n",
    "                    prv += matrix[k][j]\n",
    "                    tot[j+1] += prv\n",
    "                    ans += cnt[tot[j+1] - target]\n",
    "                    cnt[tot[j+1]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums, k):\n",
    "            cnter = defaultdict(int)\n",
    "            cnter[0] = 1\n",
    "            ans = 0\n",
    "            prefix_sum = 0\n",
    "            for num in nums:\n",
    "                prefix_sum += num\n",
    "                ans += cnter[prefix_sum - k]\n",
    "                cnter[prefix_sum] += 1\n",
    "            return ans\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            col_sum = [0] * n\n",
    "\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for col in range(n):\n",
    "                    col_sum[col] += matrix[j][col]\n",
    "                res += subarraySum(col_sum, target)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = [0] * m\n",
    "            for j in range(i, n):\n",
    "                for k in range(m):\n",
    "                    s[k] += matrix[j][k]\n",
    "                mp = defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                sum = 0\n",
    "                for x in s:\n",
    "                    sum += x\n",
    "                    ans += mp[sum - target]\n",
    "                    mp[sum] += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        res = 0\n",
    "        nrow, ncol = len(matrix), len(matrix[0])\n",
    "        nsum = [0]*ncol\n",
    "        for i in range(nrow):\n",
    "            for j in range(i, nrow):\n",
    "                for k in range(ncol):\n",
    "                    nsum[k] += matrix[j][k]\n",
    "                for k in range(ncol):\n",
    "                    tmp = 0\n",
    "                    for l in range(k, ncol):\n",
    "                        tmp += nsum[l]\n",
    "                        if tmp == target:\n",
    "                            res += 1\n",
    "            nsum = [0]*ncol\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def cal(self, arr, target):\n",
    "        res = 0\n",
    "        d = {}\n",
    "        \n",
    "        preS = [0]*len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i == 0:\n",
    "                preS[i] = arr[i]\n",
    "            else:\n",
    "                preS[i] = preS[i-1] + arr[i]\n",
    "        \n",
    "        for i in range(len(preS)):\n",
    "            if preS[i] == target:\n",
    "                res += 1\n",
    "            res += d.get(preS[i] - target, 0)\n",
    "            d[preS[i]] = d.get(preS[i], 0) + 1\n",
    "        return res\n",
    "\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(m):\n",
    "            # 上边界i\n",
    "            preSum = [0] * n\n",
    "            for j in range(i, m):\n",
    "                # 下边界j\n",
    "                # update preSum\n",
    "                for k in range(n):\n",
    "                    preSum[k] += matrix[j][k]\n",
    "                res += self.cal(preSum, target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for top in range(m):\n",
    "            rowPrefix = [0] * n\n",
    "            for bottom in range(top, m):\n",
    "                colPrefix = 0\n",
    "                colprefix_dict = {0:1}\n",
    "                for left in range(n):\n",
    "                    rowPrefix[left] += matrix[bottom][left]\n",
    "                    colPrefix += rowPrefix[left]\n",
    "                    if colPrefix - target in colprefix_dict:\n",
    "                        ans += colprefix_dict[colPrefix - target]\n",
    "                    if colPrefix in colprefix_dict:\n",
    "                        colprefix_dict[colPrefix] += 1\n",
    "                    else:\n",
    "                        colprefix_dict[colPrefix] = 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            row = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for k in range(n):\n",
    "                    row[k] += matrix[j][k]\n",
    "                s = 0\n",
    "                last = defaultdict(int) \n",
    "                last[0] = 1\n",
    "                for x in row:\n",
    "                    s += x\n",
    "                    ans += last[s - target]\n",
    "                    last[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        \n",
    "        res = 0\n",
    "        r, c = len(matrix), len(matrix[0])\n",
    "\n",
    "\n",
    "        for i in range(r):\n",
    "            tmp = [0] * c \n",
    "            for j in range(i, r):\n",
    "                mp = collections.defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                presum = 0\n",
    "                for k in range(c):\n",
    "                    tmp[k] += matrix[j][k]\n",
    "                    presum += tmp[k]\n",
    "                    res += mp.get(presum - target, 0)\n",
    "                    mp[presum] += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        if m > n:\n",
    "            matrix = list(zip(*matrix))\n",
    "            m, n = n, m\n",
    "        ans = 0\n",
    "        mp = defaultdict(int)\n",
    "        for t in range(m):\n",
    "            rowsum = [0] * n\n",
    "            for b in range(t, m):\n",
    "                mp.clear()\n",
    "                mp[0] = 1\n",
    "                colsum = 0\n",
    "                for c in range(n):\n",
    "                    rowsum[c] += matrix[b][c]\n",
    "                    colsum += rowsum[c]\n",
    "                    ans += mp.get(colsum - target, 0)\n",
    "                    mp[colsum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m ,n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(1,n):\n",
    "                matrix[i][j] += matrix[i][j-1]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                c = collections.defaultdict(int)\n",
    "                pre = 0\n",
    "                c[0]=1\n",
    "                for k in range(m):\n",
    "                    pre+= matrix[k][j]-(0 if i==0 else matrix[k][i-1])\n",
    "                    ans+=c[pre-target]\n",
    "                    c[pre]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        for left in range(m):\n",
    "            sumnum = [0]*n \n",
    "            for right in range(left, m):\n",
    "                prexi = [0]*(n+1)\n",
    "                for i in range(n):\n",
    "                    sumnum[i] += matrix[right][i]\n",
    "                dic = Counter([0])\n",
    "                pre = 0\n",
    "                for e in sumnum:\n",
    "                    pre += e\n",
    "                    if pre - target in dic:\n",
    "                        res += dic[pre-target]\n",
    "                    dic[pre] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            col_sum = [0] * n\n",
    "            for j in range(i, m):\n",
    "                seen = collections.defaultdict(int)\n",
    "                seen[0] += 1\n",
    "                area_sum = [0]\n",
    "                for k in range(n):\n",
    "                    col_sum[k] += matrix[j][k] \n",
    "                    area_sum.append(area_sum[-1] + col_sum[k])\n",
    "                    ans += seen[area_sum[-1] - target] \n",
    "                    seen[area_sum[-1]] += 1\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            cnt = Counter([0])\n",
    "            \n",
    "            cur = 0\n",
    "            ans = 0\n",
    "            for num in nums:\n",
    "                cur += num\n",
    "                if cnt[cur-k]>0:\n",
    "                    ans+=cnt[cur-k]\n",
    "                cnt[cur]+=1\n",
    "            return ans\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            t = [0]*n\n",
    "            for j in range(i,m):\n",
    "                \n",
    "                for k in range(n):\n",
    "                    t[k]+=matrix[j][k]\n",
    "                res += subarraySum(t,target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "\n",
    "        def cal(col_sum):\n",
    "            cnt = defaultdict(int)\n",
    "            ret = 0\n",
    "            pre_sum = list(accumulate(col_sum, initial = 0))\n",
    "            for x in pre_sum:\n",
    "                ret += cnt[x - target]\n",
    "                cnt[x] += 1\n",
    "            return ret\n",
    "\n",
    "        for i in range(n):\n",
    "            col_sum = [0] * m\n",
    "            for j in range(i, n):\n",
    "                for k in range(m):\n",
    "                    col_sum[k] += matrix[j][k]\n",
    "                ans += cal(col_sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            dct = Counter([0])\n",
    "            cnt, pre = 0, 0\n",
    "            for num in nums:\n",
    "                pre += num\n",
    "                if pre - k in dct:\n",
    "                    cnt += dct[pre - k]\n",
    "                dct[pre] += 1\n",
    "            return cnt\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "\n",
    "        res = 0\n",
    "        for low in range(n):\n",
    "            sums = [0] * m\n",
    "            for high in range(low, n):\n",
    "                dict = {0 : 1}\n",
    "                tot  = 0\n",
    "                for r in range(m):\n",
    "                    sums[r] += matrix[high][r]\n",
    "                    tot += sums[r]\n",
    "                    if (cur := tot - target) in dict:\n",
    "                        res += dict[cur]\n",
    "                        #dict[cur] += 1\n",
    "                    if tot not in dict:\n",
    "                        dict[tot] = 1\n",
    "                    else:\n",
    "                        dict[tot] += 1\n",
    "                #print(dict)\n",
    "        \n",
    "        return res\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        Row, Col = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        for L in range(Col):        #L为左边界\n",
    "            row_sum = [0 for _ in range(Row)]   #L为左边界R为右边界，各行的和\n",
    "            for R in range(L, Col):\n",
    "                for r in range(Row):\n",
    "                    row_sum[r] += matrix[r][R]\n",
    "                \n",
    "                pre_sum_cnt_dict = collections.defaultdict(int)\n",
    "                pre_sum_cnt_dict[0] = 1  # 初始时，累加和为0的情况为1\n",
    "                pre_sum = 0\n",
    "                for row_sum_val in row_sum:\n",
    "                    pre_sum += row_sum_val\n",
    "                    if pre_sum - target in pre_sum_cnt_dict:\n",
    "                        res += pre_sum_cnt_dict[pre_sum - target]\n",
    "                    pre_sum_cnt_dict[pre_sum] += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        if m > n:\n",
    "            matrix = list(zip(*matrix))\n",
    "            m, n = n, m\n",
    "        ans = 0\n",
    "        for t in range(m):\n",
    "            rowsum = [0] * n\n",
    "            for b in range(t, m):\n",
    "                mp = defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                colsum = 0\n",
    "                for c in range(n):\n",
    "                    rowsum[c] += matrix[b][c]\n",
    "                    colsum += rowsum[c]\n",
    "                    ans += mp.get(colsum - target, 0)\n",
    "                    mp[colsum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums, k):\n",
    "            mp = Counter([0])\n",
    "            count = 0\n",
    "            pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "\n",
    "        # 二维前缀和\n",
    "        m , n = len(matrix),len(matrix[0])\n",
    "        s = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1] + matrix[i-1][j-1]\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for top in range(m+1):\n",
    "            for bottom in range(top+1,m+1):\n",
    "                section_presum = defaultdict(int)\n",
    "                section_presum[0] = 1\n",
    "                for col in range(1, n + 1):\n",
    "                    # 一维前缀\n",
    "                    prefix = s[bottom][col] - s[top][col]\n",
    "                    res += section_presum[prefix - target]\n",
    "                    section_presum[prefix] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def sumarraySum(nums, k):\n",
    "            mp = collections.Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n \n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                # 列向右逐渐移动\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += sumarraySum(total, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, mx: List[List[int]], t: int) -> int:\n",
    "        m,n=len(mx),len(mx[0])\n",
    "        tmp=[[0]*(n+1) for i in range(m+1)]\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tmp[i+1][j+1]=tmp[i][j+1]+tmp[i+1][j]+mx[i][j]-tmp[i][j]\n",
    "        for i in range(m):\n",
    "            for ii in range(i+1,m+1):\n",
    "                temp = [tmp[ii][j]-tmp[i][j] for j in range(n+1)]\n",
    "                for j in range(n):\n",
    "                    for jj in range(j+1,n+1):\n",
    "                        if temp[jj]-temp[j]==t:\n",
    "                            res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pref_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pref_sum[i][j] = pref_sum[i-1][j] + pref_sum[i][j-1] - pref_sum[i-1][j-1] + matrix[i-1][j-1]\n",
    "        \n",
    "        res = 0\n",
    "        for top in range(1, m + 1):\n",
    "            for bottom in range(top, m + 1):\n",
    "                area_freq = {0:1}\n",
    "                for r in range(1, n + 1):\n",
    "                    cur_area = pref_sum[bottom][r] - pref_sum[top-1][r]\n",
    "                    res += area_freq.get(cur_area - target, 0)\n",
    "                    area_freq[cur_area] = area_freq.get(cur_area, 0) + 1          \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for i in range(n - 1):\n",
    "                row[i + 1] += row[i]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                c = collections.defaultdict(int)\n",
    "                cur, c[0] = 0, 1\n",
    "                for k in range(m):\n",
    "                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    res += c[cur - target]\n",
    "                    c[cur] += 1\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def cal(self, arr, target):\n",
    "        n = len(arr)\n",
    "        d = {}\n",
    "        res = 0\n",
    "        left = [0]*n\n",
    "        left[0] = arr[0]\n",
    "        for i in range(1, n):\n",
    "            left[i] = left[i-1] + arr[i]\n",
    "\n",
    "        for i in range(n):\n",
    "            if left[i] == target:\n",
    "                res += 1\n",
    "            res += d.get(left[i] - target, 0)\n",
    "            d[left[i]] = d.get(left[i], 0) + 1\n",
    "\n",
    "        return res\n",
    "\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        res = 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            preSum = [0]*n\n",
    "            for j in range(i, m):\n",
    "                # update preSum\n",
    "                for k in range(n):\n",
    "                    preSum[k] += matrix[j][k]\n",
    "                res += self.cal(preSum, target)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "\n",
    "        n,m = len(matrix),len(matrix[0])\n",
    "        presum = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(1,n + 1):\n",
    "            for j in range(1,m + 1):\n",
    "                presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + matrix[i - 1][j - 1]\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        for x1 in range(1,n + 1):\n",
    "            for x2 in range(x1,n + 1):\n",
    "                dict1 = collections.defaultdict(int)\n",
    "\n",
    "                for r in range(1,m + 1):\n",
    "                    cur = presum[x2][r] - presum[x1 - 1][r]\n",
    "                    if cur == target:\n",
    "                        ans += 1\n",
    "                    \n",
    "                    ans += dict1[cur - target]\n",
    "                    dict1[cur] += 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for t in range(m):\n",
    "            rowsum = [0] * n\n",
    "            for b in range(t, m):\n",
    "                mp = defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                colsum = 0\n",
    "                for c in range(n):\n",
    "                    rowsum[c] += matrix[b][c]\n",
    "                    colsum += rowsum[c]\n",
    "                    ans += mp.get(colsum - target, 0)\n",
    "                    mp[colsum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def sumarraySum(nums, k):\n",
    "            mp = collections.Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            total = [0] * n \n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += sumarraySum(total, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        # 二维前缀和\n",
    "        f = [[0]*(n + 1) for _ in range(m + 1)]\n",
    "        for i,row in enumerate(matrix):\n",
    "            for j,x in enumerate(row):\n",
    "                f[i + 1][j + 1] = f[i][j + 1] + f[i + 1][j] - f[i][j] + x\n",
    "        ans = 0\n",
    "        # 枚举子矩阵上下边界\n",
    "        for up in range(m):\n",
    "            for bo in range(up,m):\n",
    "                d = defaultdict(int)\n",
    "                # 枚举右边界，此处相当于两数之和\n",
    "                for i in range(n):\n",
    "                    # 右下角坐标 (bo,i) 左上角坐标 (up,0)\n",
    "                    s = f[bo + 1][i + 1] - f[up][i + 1]\n",
    "                    if s == target:\n",
    "                        ans += 1\n",
    "                    ans += d[s - target]\n",
    "                    d[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for c in range(C - 1):\n",
    "                row[c + 1] += row[c]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(C):\n",
    "            for j in range(i, C): # turn to 1d array\n",
    "                nums = [matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0) for k in range(R)]\n",
    "                presum, d = 0, {0: 1}\n",
    "                for num in nums:\n",
    "                    presum += num\n",
    "                    if presum - target in d:\n",
    "                        res += d[presum - target]\n",
    "                    d[presum] = d.get(presum, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "\n",
    "        res = 0\n",
    "        for low in range(n):\n",
    "            sums = [0] * m\n",
    "            for high in range(low, n):\n",
    "                dict = {0 : 1}\n",
    "                tot  = 0\n",
    "                for r in range(m):\n",
    "                    sums[r] += matrix[high][r]\n",
    "                    tot += sums[r]\n",
    "                    if (cur := tot - target) in dict:\n",
    "                        res += dict[cur]\n",
    "                        #dict[cur] += 1\n",
    "                    if tot not in dict:\n",
    "                        dict[tot] = 1\n",
    "                    else:\n",
    "                        dict[tot] += 1\n",
    "                #print(dict)\n",
    "        \n",
    "        return res\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        res = 0\n",
    "        \n",
    "        def prefixSum(nums,target):\n",
    "            n = len(nums)\n",
    "            prefix = 0\n",
    "            ans = 0\n",
    "            dic = defaultdict(int)\n",
    "            dic[0]=1\n",
    "            for i in nums:\n",
    "                prefix+=i\n",
    "                ans += dic[prefix-target]\n",
    "                dic[prefix]+=1\n",
    "            return ans\n",
    "        \n",
    "        for x in range(m):\n",
    "            nums = [0]*n\n",
    "            for i in range(x,m):\n",
    "                for j in range(n):\n",
    "                    nums[j]+=matrix[i][j]\n",
    "                res += prefixSum(nums,target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for i in range(n - 1):\n",
    "                row[i + 1] += row[i]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                c = collections.defaultdict(int)\n",
    "                cur, c[0] = 0, 1\n",
    "                for k in range(m):\n",
    "                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    ans += c[cur - target]\n",
    "                    c[cur] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def pref_sum(a: List[int]) -> None:\n",
    "            for i in range(1, len(a)):\n",
    "                a[i] += a[i - 1]\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for r in matrix:\n",
    "           pref_sum(r)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                cumu = 0\n",
    "                cnt = Counter()\n",
    "                cnt[0] = 1\n",
    "                for k in range(m):\n",
    "                    s = matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    cumu += s\n",
    "                    ans += cnt[cumu - target]\n",
    "                    cnt[cumu] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class prefix_sum:\n",
    "    #二维前缀和\n",
    "    def __init__(self, mat: int):\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        self.qz=[[0]*(n+1) for _ in range(m+1)]\n",
    "        qz=self.qz\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                qz[i][j]=qz[i-1][j]+qz[i][j-1]-qz[i-1][j-1]+mat[i-1][j-1]\n",
    "\n",
    "    #查询以(r1,c1)为左上角，(r2,c2)为右下角的矩形区间内所有值的和\n",
    "    def find(self,r1,c1,r2,c2):  \n",
    "        qz=self.qz\n",
    "        return qz[r2+1][c2+1]-qz[r2+1][c1]-qz[r1][c2+1]+qz[r1][c1]\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        res=0\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        pre=prefix_sum(matrix)\n",
    "        for i in range(m):\n",
    "            for j in range(i,m):\n",
    "                d=defaultdict(int)\n",
    "                d[0]=1\n",
    "                for k in range(n):\n",
    "                    p=pre.find(i,0,j,k)\n",
    "                    res+=d[p-target]\n",
    "                    d[p]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for c in range(C - 1):\n",
    "                row[c + 1] += row[c]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(C):\n",
    "            for j in range(i, C): # turn to 1d array\n",
    "                nums = [matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0) for k in range(R)]\n",
    "                presum, d = 0, {0: 1}\n",
    "                for n in nums:\n",
    "                    presum += n\n",
    "                    if presum - target in d:\n",
    "                        res += d[presum - target]\n",
    "                    d[presum] = d.get(presum, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        res = 0\n",
    "        \n",
    "        def prefixSum(nums,target):\n",
    "            n = len(nums)\n",
    "            prefix = 0\n",
    "            ans = 0\n",
    "            dic = defaultdict(int)\n",
    "            dic[0]=1\n",
    "            for i in nums:\n",
    "                prefix+=i\n",
    "                ans += dic[prefix-target]\n",
    "                dic[prefix]+=1\n",
    "            return ans\n",
    "        \n",
    "        for x in range(m):\n",
    "            nums = [0]*n\n",
    "            for i in range(x,m):\n",
    "                for j in range(n):\n",
    "                    nums[j]+=matrix[i][j]\n",
    "                res += prefixSum(nums,target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        suf = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                suf[i][j] = suf[i - 1][j] + suf[i][j - 1] - suf[i - 1][j - 1] + matrix[i - 1][j - 1]\n",
    "\n",
    "        ans = 0\n",
    "        for top in range(1, m + 1):\n",
    "            for bot in range(top, m + 1):\n",
    "                cnt = Counter()\n",
    "                cnt[0] = 1\n",
    "                for i in range(1, n + 1):\n",
    "                    x = suf[bot][i] - suf[top - 1][i]\n",
    "                    ans += cnt[x - target]\n",
    "                    cnt[x] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def subarraySum(nums: List[int], k: int) -> int:\n",
    "            mp = Counter([0])\n",
    "            count = pre = 0\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                if pre - k in mp:\n",
    "                    count += mp[pre - k]\n",
    "                mp[pre] += 1\n",
    "            print(mp)\n",
    "            return count\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        # 枚举上边界\n",
    "        for i in range(m):\n",
    "            # print(f'上边界：{i}')\n",
    "\n",
    "            total = [0] * n\n",
    "            # 枚举下边界\n",
    "            for j in range(i, m):\n",
    "                # print(f'下边界: {j}')\n",
    "                for c in range(n):\n",
    "                    # 更新每列的元素和\n",
    "                    total[c] += matrix[j][c]\n",
    "                ans += subarraySum(total, target)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        Row, Col = len(matrix), len(matrix[0])\n",
    "\n",
    "        presum = [[0 for _ in range(Col + 1)] for _  in range(Row + 1)]\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                presum[r+1][c+1] = presum[r+1][c] + presum[r][c+1] - presum[r][c] + matrix[r][c]\n",
    "\n",
    "        res = 0\n",
    "        for U in range(0, Row + 1):\n",
    "            for D in range(U + 1, Row + 1):   #2块水平的木板夹住的区域\n",
    "                section_presum = defaultdict(int)       #2块水平木板中间，矩形右边界从左到右的前缀和\n",
    "                section_presum[0] = 1\n",
    "                for c in range(1, Col + 1):\n",
    "                    prefix = presum[D][c] - presum[U][c]\n",
    "                    res += section_presum[prefix - target]\n",
    "                    section_presum[prefix] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "\n",
    "        # 二维前缀和\n",
    "        m , n = len(matrix),len(matrix[0])\n",
    "        s = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1] + matrix[i-1][j-1]\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for top in range(m+1):\n",
    "            for bottom in range(top+1,m+1):\n",
    "                section_presum = defaultdict(int)\n",
    "                section_presum[0] = 1\n",
    "                for col in range(1, n + 1):\n",
    "                    # 一维前缀\n",
    "                    prefix = s[bottom][col] - s[top][col]\n",
    "                    # 如果s - target在哈希表中，则s - target = x，等价于s - x = target，\n",
    "                    res += section_presum[prefix - target]\n",
    "                    section_presum[prefix] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        trans = m > n\n",
    "        if trans: m, n = n, m\n",
    "        colsum = [[0] * n for _ in range(m+1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, x in enumerate(row):\n",
    "                if trans:\n",
    "                    colsum[j+1][i] = colsum[j][i] + x\n",
    "                else:\n",
    "                    colsum[i+1][j] = colsum[i][j] + x\n",
    "\n",
    "        ans = 0\n",
    "        for t in range(m):\n",
    "            for b in range(t+1, m+1):\n",
    "                mp = defaultdict(int)\n",
    "                mp[0] = 1\n",
    "                s = 0\n",
    "                for r in range(n):\n",
    "                    s += colsum[b][r] - colsum[t][r]\n",
    "                    ans += mp.get(s - target, 0)\n",
    "                    mp[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix, target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for i in range(1, n):\n",
    "                row[i] += row[i - 1]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                c = collections.Counter({0: 1})\n",
    "                cur = 0\n",
    "                for k in range(m):\n",
    "                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    res += c[cur - target]\n",
    "                    c[cur] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        # 二维前缀和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre_sum[i + 1][j + 1] = pre_sum[i + 1][j] + pre_sum[i][j + 1] - pre_sum[i][j] + matrix[i][j]\n",
    "\n",
    "        # 结合一维前缀和\n",
    "        for up in range(m):\n",
    "            for down in range(up, m):\n",
    "                cnt = Counter([0])\n",
    "                sm = 0\n",
    "                for right in range(n):\n",
    "                    sm += pre_sum[down + 1][right + 1] + pre_sum[up][right] - pre_sum[up][right + 1] - pre_sum[down + 1][right]\n",
    "                    ans += cnt[sm - target]\n",
    "                    cnt[sm] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix, target):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for i in range(n - 1):\n",
    "                row[i + 1] += row[i]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                c = collections.defaultdict(int)\n",
    "                cur, c[0] = 0, 1\n",
    "                for k in range(m):\n",
    "                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    ans += c[cur - target]\n",
    "                    c[cur] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        cumsum = [[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                cumsum[i][j] = cumsum[i-1][j] + cumsum[i][j-1] - cumsum[i-1][j-1] + matrix[i-1][j-1]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i, n+1):\n",
    "                mem = {0:1}\n",
    "                for k in range(1, m+1):\n",
    "                    cur = cumsum[j][k] - cumsum[i-1][k]\n",
    "                    ans += mem.get(cur-target, 0)\n",
    "                    mem[cur] = mem.get(cur, 0) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class PreFixSumMatrix:\n",
    "    def __init__(self, mat):\n",
    "        self.mat = mat\n",
    "        # 二维前缀和\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        self.pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.pre[i + 1][j + 1] = self.pre[i][j + 1] + \\\n",
    "                    self.pre[i + 1][j] - self.pre[i][j] + mat[i][j]\n",
    "\n",
    "    def query(self, xa, ya, xb, yb):\n",
    "        # 二维子矩阵和查询，索引从 0 开始，左上角 [xa, ya] 右下角 [xb, yb]\n",
    "        return self.pre[xb + 1][yb + 1] - self.pre[xb +\n",
    "                                                   1][ya] - self.pre[xa][yb + 1] + self.pre[xa][ya]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = PreFixSumMatrix(matrix)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                dct = defaultdict(int)\n",
    "                dct[0] = 1\n",
    "                for k in range(n):\n",
    "                    cur = pre.query(i, 0, j, k)\n",
    "                    ans += dct[cur-target]\n",
    "                    dct[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        # 构建二维前缀和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        prefix = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1,n+1):\n",
    "                prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] + matrix[i-1][j-1] - prefix[i-1][j-1]\n",
    "        print(prefix)\n",
    "        # 遍历top, bottom, right\n",
    "        # 哈希查找left\n",
    "        ans = 0\n",
    "        for top in range(1, m+1): \n",
    "            for bottom in range(top, m+1):  \n",
    "                di = {} \n",
    "                for right in range(0, n+1): \n",
    "                    cur = prefix[bottom][right] - prefix[top-1][right]\n",
    "                    if cur - target in di: \n",
    "                        ans += di[cur - target]  \n",
    "                    if cur in di:\n",
    "                        di[cur] += 1\n",
    "                    else:\n",
    "                        di[cur] = 1\n",
    "        return ans  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "presum = [[0] * 100 for _ in range(100)]\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                p1 = presum[i - 1][j] if i > 0 else 0\n",
    "                p2 = presum[i][j - 1] if j > 0 else 0\n",
    "                p3 = presum[i - 1][j - 1] if i > 0 and j > 0 else 0\n",
    "                presum[i][j] = matrix[i][j] + p1 + p2 - p3\n",
    "\n",
    "        ret = 0\n",
    "        for x1 in range(m):\n",
    "            for x2 in range(x1, m):\n",
    "                areas = [0]\n",
    "\n",
    "                for y in range(n):\n",
    "                    p1 = presum[x1 - 1][y] if x1 > 0 else 0\n",
    "                    a = presum[x2][y] - p1\n",
    "                    areas.append(a)\n",
    "\n",
    "                cnts = Counter(areas)\n",
    "\n",
    "                for a in areas:\n",
    "                    cnts[a] -= 1\n",
    "                    ret += cnts[a + target]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n",
    "        def get_area(i1, j1, i2, j2):\n",
    "            return dp[i2 + 1][j2 + 1] - dp[i1][j2 + 1] - dp[i2 + 1][j1] + dp[i1][j1]\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]  # 2D pre-sum\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i + 1][j + 1] = matrix[i][j] + dp[i][j + 1] + dp[i + 1][j] - dp[i][j]\n",
    "        cnt = 0\n",
    "        for l in range(n):\n",
    "            for r in range(l, n):\n",
    "                counter = defaultdict(int)\n",
    "                counter[0] = 1\n",
    "                for down in range(m):\n",
    "                    area = get_area(0, l, down, r)\n",
    "                    cnt += counter[area - target]\n",
    "                    counter[area] += 1\n",
    "        return cnt\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
